#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <climits>

using namespace std;

// 无重复长度的最长字串
class Solution
{
public:
    int lengthOfLongestSubstring(string s)
    {
        unordered_map<char, int> hash;
        int n = s.size(), left = 0, right = 0;
        int ans = 0;
        while (right < n)
        {
            hash[s[right]]++;
            while (hash[s[right]] > 1)
            {
                hash[s[left]]--;
                left++;
            }
            ans = max(ans, right - left + 1);
            right++;
        }

        return ans;
    }
};

// 找到字符串中所有字母异位词
class Solution
{
public:
    vector<int> findAnagrams(string s, string p)
    {
        // 在字符串 s 中构造⼀个⻓度为与字符串 p 
        // 的⻓度相同的滑动窗⼝，并在滑动中维护窗⼝中每种字⺟的数量
        // 当窗⼝中每种字⺟的数量与字符串 p 中每种字⺟的数量相同时，
        // 则说明当前窗⼝为字符串 p的异位词；
        // hash1统计p中每个字符出现的个数
        // hash2统计窗⼝⾥⾯的每⼀个字符出现的个数
        vector<int> ans;
        int hash1[26] = {0}, hash2[26] = {0};
        for (auto x : p)
        {
            hash1[x - 'a']++;
        }
        int m = p.size(), count = 0;
        int left = 0, right = 0, n = s.size();
        while (right < n)
        {
            char in = s[right] - 'a';
            hash2[in]++;
            count++;
            while (hash2[in] > hash1[in])
            {
                char out = s[left] - 'a';
                hash2[out]--;
                left++;
                count--;
            }

            if (count == m)
                ans.push_back(left);
            right++;
        }

        return ans;
    }
};

// 和为k的子数组
class Solution
{
public:
    int subarraySum(vector<int> &nums, int k)
    {
        // 前缀和出现的次数[0,i-1]
        unordered_map<int, int> hash;
        int ans = 0, sum = 0;
        hash[0] = 1;
        for (auto x : nums)
        {
            sum += x;
            if (hash.count(sum - k))
            {
                ans += hash[sum - k];
            }
            hash[sum]++;
        }

        return ans;
    }
};

// 滑动窗口最大值
class Solution
{
public:
    vector<int> maxSlidingWindow(vector<int> &nums, int k)
    {
        vector<int> ans;
        int n = nums.size(), maxnum = INT_MIN;
        for (int i = 0; i < k; i++)
        {
            if (nums[i] > maxnum)
                maxnum = nums[i];
        }
        ans.push_back(maxnum);
        for (int i = k; i < n; ++i)
        {
            if (nums[i] > maxnum)
            {
                ans.push_back(nums[i]);
                maxnum = nums[i];
            }
            else
            {
                if (maxnum == nums[i - k])
                {
                    int maxtmp = INT_MIN;
                    for (int j = i - k + 1; j <= i; j++)
                    {
                        maxtmp = max(maxtmp, nums[j]);
                    }
                    ans.push_back(maxtmp);
                    maxnum = maxtmp;
                }
                else
                {
                    ans.push_back(maxnum);
                }
            }
        }
        return ans;
    }
};

class Solution
{
public:
    vector<int> maxSlidingWindow(vector<int> &nums, int k)
    {
        priority_queue<pair<int, int>> pq;
        vector<int> ans;
        int n = nums.size();
        for (int i = 0; i < k; i++)
        {
            pq.emplace(nums[i], i);
        }

        ans.push_back(pq.top().first);
        for (int i = k; i < n; i++)
        {
            pq.emplace(nums[i], i);
            while (pq.top().second <= i - k)
            {
                pq.pop();
            }
            ans.push_back(pq.top().first);
        }

        return ans;
    }
};

// 最小覆盖子串
class Solution
{
public:
    string minWindow(string s, string t)
    {
        unordered_map<char, int> hash1;
        unordered_map<char, int> hash2;
        // 统计t字符串中字符出现的种类
        int kind = 0;
        for (auto x : t)
        {
            hash1[x]++;
            if (hash1[x] == 1)
                kind++;
        }

        int n = s.size(), left = 0, right = 0;
        int count = 0, begin = -1, minlen = INT_MAX;
        while (right < n)
        {
            char in = s[right];
            hash2[in]++;
            if (hash1.count(in) && hash1[in] == hash2[in])
            {
                count++;
            }
            while (count == kind)
            {
                if (right - left + 1 < minlen)
                {
                    minlen = min(minlen, right - left + 1);
                    begin = left;
                }
                char out = s[left];
                if (hash1.count(out) && hash1[out] == hash2[out])
                {
                    count--;
                }
                hash2[out]--;
                left++;
            }
            right++;
        }

        return begin == -1 ? "" : s.substr(begin, minlen);
    }
};
